package com.cat.dataStructure02;

import java.util.HashSet;
import java.util.Set;

class Solution50 {
    int n, m;
    int[][] g;

    public int largestMagicSquare(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        g = grid;
        for (int k = Math.min(n, m); k > 1; k--) {
            if (check(k)) {
                return k;
            }
        }
        return 1;
    }

    boolean check(int k) {
        int maxR = n - k, maxC = m - k;
        for (int i = 0; i <= maxR; i++) {
            for (int j = 0; j <= maxC; j++) {
                if (isMagic(i, j, k)) {
                    return true;
                }
            }
        }
        return false;
    }

    boolean isMagic(int x, int y, int k) {
        Set<Integer> set = new HashSet<>();
        int[] row = new int[k], col = new int[k];
        int d1 = 0, d2 = 0;
        for (int i = 0; i < k; i++) {
            for (int j = 0; j < k; j++) {
                row[i] += g[x + i][y + j];
                col[j] += g[x + i][y + j];
                if (i == j) { // 正对角线
                    d1 += g[x + i][y + j];
                }
                if (i + j == k - 1) { // 斜对角线 
                    d2 += g[x + i][y + j];
                }
            }
        }
        set.add(d1);
        set.add(d2);
        for (int i = 0; i < k; i++) {
            set.add(row[i]);
            set.add(col[i]);
        }
        return set.size() == 1;
    }
}